/*
*
*
* This Header File Is Used In Huffman Compression file
*         -Create Huffman tree
*         -Create header For Huffman Output File
*
*  Author : Vishwajeet C. Dusane(dusanevishwajeet@yahoo.co.in)
*/



class Tree
{

 //variable
   private:


 //method
   private:
	  void init(struct list **);


 //variable
   public:

 //method
   public:

	  int 	 	make_list(struct list **,char *);
	  int 		find_min(struct list **,struct list **,struct list **);
	  void 		create_header(struct header **,struct list *);
	  void 		code_tree(struct list *,int ,int );
	  void 		create_tree(struct list **,struct list **,struct list **);
	  void 		free_list(struct list **);
      void      reconstruct_header(struct header **,char,unsigned long ,unsigned int );

 };



//----------------------------------------------------------------------
//Defination of declared Methods

int Tree::make_list(struct list **head,char *ch)
{
	struct list *temp=*head,*temp1;
	while(temp!=NULL)
	{
	 if(temp->ch==*ch)
	 {
	   temp->cnt++;
	   return 0;
	  }
	 else
	  temp=temp->next;
	}
	temp=*head;
	if(temp==NULL)
	{
	  temp=(struct list *)malloc(sizeof(struct list));
	   init(&temp);
	   temp->prev=NULL;
	   temp->ch=*ch;
	   *head=temp;
	}
	else
	{
	  while(temp->next!=NULL)
	   temp=temp->next;
	  temp1=(struct list *)malloc(sizeof(struct list));
	  init(&temp1);
	  temp1->prev=temp;
	  temp1->ch=*ch;
	  temp->next=temp1;
	}
	return 0;
}
//=============================================================================

//Initialize the structure Starts
void Tree::init(struct list **temp)
{


	  temp->cnt=1;
	  temp->st='n';
	  temp->isparent=0;
	  temp->code=0;
	  temp->depth=0;
	  temp->next=NULL;
	  temp->lchild=NULL;
	  temp->rchild=NULL;


}


//This function is Used for Finding the Two Nodes having Minimum Frequencies      From List of Characters
int Tree::find_min(struct list **head,struct list **min1,struct list **min2)
{
   struct list *temp;

   while((*min1)->st=='s')
	 (*min1)=(*min1)->next;
   while((*min2)->st=='s')
	 (*min2)=(*min2)->next;
   if((*min1)==(*min2))
   {
	  if((*min1)->next==NULL)
	   return 1;
	  else
	   do
	   {
	(*min2)=(*min2)->next;
	   }while((*min2)->st!='n'&&(*min2)->next!=NULL);

   }
   if((*min1)->cnt>(*min2)->cnt)
	{
	 temp=(*min1);
	 (*min1)=(*min2);
	 (*min2)=temp;
	}

   temp=*head;
   while(temp!=NULL)
   {
	 if(temp->st=='n')
	 {
	  if(temp->cnt <= (*min1)->cnt&&temp->ch!=(*min1)->ch)
	  {
	 if(temp!=(*min2))
	 {
	  (*min2)=(*min1);
	  (*min1)=temp;
	 }
	  temp=temp->next;
	  continue;
	  }
	  if(temp->cnt <= (*min2)->cnt&&temp->ch!=(*min2)->ch)
	  {
	 if(temp!=(*min1))
	  (*min2)=temp;
	  }
	 }
	  temp=temp->next;
   }
   (*min1)->st='s';
   (*min1)->isparent=1;
   (*min2)->st='s';
   (*min2)->isparent=1;
   if((*min1)==(*min2))
	 return 1;
   return 0;
}
//=============================================================================




//This Function is Used for Creation of Header of Compression
void Tree::create_header(struct header **head,struct list *node)
{
	struct header *temp=*head,*temp1;
	if(temp==NULL)
	{
	 temp=(struct header *)malloc(sizeof(struct header));
	 temp->ch=node->ch;
	 temp->code=node->code;
	 temp->depth=node->depth;
	 temp->cnt=node->cnt;
	 temp->tot_node=1;
	 temp->next=NULL;
	 *head=temp;
	}
	else
	{
	 while(temp->next!=NULL)
	temp=temp->next;
	 temp1=(struct header *)malloc(sizeof(struct header));
	 temp1->ch=node->ch;
	 temp1->code=node->code;
	 temp1->depth=node->depth;
	 temp1->cnt=node->cnt;
	 temp1->tot_node=0;
	 temp1->next=NULL;
	 temp->next=temp1;
	 (*head)->tot_node++;
	}
}
//=============================================================================



//This Function is Used To Code the Huffman's Tree
void Tree::code_tree(struct list *root,int codesofar,int depth)
{

  if(root->lchild==NULL&&root->rchild==NULL)
  {
	  root->code=codesofar;
	  root->depth=depth;
	  depth=0;
	  create_header(&head_header,root);
  }
  else
  {
	 code_tree(root->lchild,(codesofar*2),depth+1);
	 code_tree(root->rchild,((codesofar*2)+1),depth+1);
  }
}
//==============================================================================


//This Function is used for Creation of Huffman's Tree
void Tree::create_tree(struct list **head,struct list **min1,struct list **min2)
{
   struct list *temp=*head,*temp1;
   while(temp->next!=NULL)
   temp=temp->next;
   temp1=(struct list *)malloc(sizeof(struct list));
   temp1->cnt=((*min1)->cnt + (*min2)->cnt);
   temp1->st='n';
   temp1->lchild=(*min1);
   temp1->rchild=(*min2);
   temp1->isparent=0;
   temp1->code=0;
   temp1->depth=0;
   temp1->next=NULL;
   temp->next=temp1;
}
//=============================================================================


//This Function is Used for Freeing the List of Characters
void Tree::free_list(struct list **head)
{
   struct list *temp=*head;
   while(temp->next!=NULL)
	temp=temp->next;
   while(temp->prev!=NULL)
   {
	 temp=temp->prev;
	 free(temp->next);
   }
   free(*head);
}

//This function is used to Construct the Header
void Tree::reconstruct_header(head,chr,chr_code,chr_depth)
struct header **head;
char chr;
unsigned long chr_code;
unsigned int chr_depth;
{
   struct header *temp=*head,*temp1;
   if(*head==NULL)
   {
     temp=(struct header *)malloc(sizeof(struct header));
     temp->ch=chr;
     temp->code=chr_code;
     temp->depth=chr_depth;
     temp->tot_node=1;
     temp->next=NULL;
     *head=temp;
   }
   else
   {
     while(temp->next!=NULL)
       temp=temp->next;

     temp1=(struct header *)malloc(sizeof(struct header));
     temp1->ch=chr;
     temp1->code=chr_code;
     temp1->depth=chr_depth;
     temp1->tot_node=-1;
     temp1->next=NULL;
     temp->next=temp1;
     (*head)->tot_node++;
   }
}
//=============================================================================
